<TITLE>prob005: low autocorrelation binary sequences</TITLE>
<HR><!------------------------------------------------------------------------>
<CENTER>
<H1>prob005: low autocorrelation binary sequences</H1>

<TABLE>
<TR> <TD> proposed by
     <TD ALIGN=LEFT> <A HREF="http://www.cs.york.ac.uk/~tw">
          <B>Toby Walsh</B></A> 
          <ADDRESS><a href="mailto:tw@cs.york.ac.uk">
          tw@cs.york.ac.uk</a></ADDRESS>
</TABLE>
</CENTER>
<HR><!------------------------------------------------------------------------>
<H3> Specification </H3>

<TT>
These problems have many practical applications in communications and
electrical engineering. The objective is to construct a binary sequence S_i
of length n that minimizes the autocorrelations between bits. Each bit in the
sequence takes the value +1 or -1. 
With non-periodic (or open) boundary
conditions, 
the k-th autocorrelation, C_k
is defined to be sum(i,0,n-k-1, S_i * S_i+k). 
With periodic (or cyclic) boundary
conditions, the k-th autocorrelation, C_k
is defined to be sum(i,0,n-1, S_i * S_((i+k)mod n)). 
The aim is to minimize the sum of the 
squares of these autocorrelations. That is,
to minimize E=sum(k,1,n-1,C_k^2). 


</TT>


<HR><!------------------------------------------------------------------------>

<UL>

 <A HREF="../../index.html"> Back</A> to CSPLib home page.


